/**
 * Parser.java
 *
 * Created by Chad Cross on 4/5/09.
 * 
 * @author Chad Cross
 * @version 1.4
 *
 * The parser takes in a regular expression and returns
 * a data structure representing the resulting NFA.  Currently
 * it only handles the *, union, and concatenation operations.
 *
 * Adapted from Amer Gerzic's regex library: http://www.amergerzic.com/page/Free-Downloads.aspx
 * Licensed under the Code Project Open License: http://www.codeproject.com/info/cpol10.aspx
 *
 */

package jmai.parser;

import java.util.*;

public class Parser {

	/** Holds operators in the regex */
	@SuppressWarnings("unchecked")
	private Stack operatorStack = new Stack();
	
	/** Holds expression in the regex */
	@SuppressWarnings("unchecked")
	private Stack expressionStack = new Stack();
	
	/** Holds the index of the next state of the NFA */
	private int nextStateIndex = 0;
	
	/** A set that contains all of the input characters in the regex */
	@SuppressWarnings("unchecked")
	public TreeSet treeSetInput = new TreeSet();
	
	/** The default constructor */
	public Parser() {
	
	}//end Parser constructor
	
	/** 
	 * Takes input from the user and converts it into an
	 * array list
	 * @param inputString the regex to be converted
	 * @return ArrayList
	 */
	@SuppressWarnings("unchecked")
	public ArrayList<?> convertToNFA(String inputString) {

		/** Used to keep track of a concatenation operator */
		boolean isConcat = false;
		
		/** Make sure the stacks are empty before doing anything */
		operatorStack = new Stack();
		expressionStack = new Stack();
		
		/** Clear the input character set */
		treeSetInput = new TreeSet();
		
		/** Reset the index variable */
		nextStateIndex = 0;
		
		/** 
		 * For the input string, check each single character to
		 * see if it is an operator or input character
		 */
		for (int i = 0; i < inputString.length(); ++i) {

			/** Grab the first token from the input string */
			char aToken = inputString.charAt(i);
			
			/** Verify that the token is an input character or operator */
			if (isInputToken(aToken)) {
				if(isConcat) {
					if(operatorStack.empty()) {
						operatorStack.push(new Character('+'));
					}//end if
					else {
						Character anOperator = (Character)operatorStack.peek();
						while (compareOperator('+', anOperator.charValue()) <= 0) {
							
							operatorEvaluator();
							
							if(operatorStack.empty()) {
								break;
							}//end if
							anOperator = (Character)operatorStack.peek();
						}//end while loop
						operatorStack.push(new Character('+'));
					}//end else
				}//end if
				
				inputStackPush(Character.toString(aToken));
				
				isConcat = true;
			}//end if
			
			else if (operatorStack.empty()) {
				if (isConcat) {
					if(aToken == '(') {
						operatorStack.push(new Character('+'));
					}//end if
				}//end if
				
				if((aToken == '*') || (aToken == '$') || (aToken == '?') || (aToken == ')'))  {
					isConcat = true;
				}//end if
				else {
					isConcat = false;
				}//end else
				//if(aToken == '+') {
				//	operatorStack.push(new Character ('+'));
				//}
				//else {
					operatorStack.push(new Character(aToken));
				//}
			}//end else if
			
			else if (checkForLeftParen(aToken)) {
				if (isConcat) {

					Character anOperator = (Character)operatorStack.peek();
					
					while(compareOperator('+', anOperator.charValue()) <= 0) {
					
						operatorEvaluator();
						
						if(operatorStack.empty()) {
							break;
						}//end if
						
						anOperator = (Character)operatorStack.peek();
					}
					
					operatorStack.push(new Character('+'));
				}//end if
				
				/** Push a left parenthesis on the stack */
				operatorStack.push(new Character(aToken));
				
				/** A left parenthesis does not imply concatenation */
				isConcat = false;
				
			}//end else if
			else if (checkForRightParen(aToken)) {
				Character anOperator = (Character)operatorStack.peek();
				
				while(!checkForLeftParen(anOperator.charValue())) {

					operatorEvaluator();
					
					if(operatorStack.empty()) {
						break;
					}//end if
					
					anOperator = (Character)operatorStack.peek();
				}//end while
				
				/** Pop the left paren */
				operatorStack.pop();
				
				isConcat = true;
			}//end else if
			else {
				Character anOperator = (Character)operatorStack.peek();
				
				while(compareOperator(aToken, anOperator.charValue()) <= 0) {
					
					operatorEvaluator();
					
					if(operatorStack.empty()){
						break;
					}//end if
					
					anOperator = (Character)operatorStack.peek();
				}//end while
				
				operatorStack.push(new Character(aToken));
				
				if (aToken == '*' || (aToken == '$') || (aToken == '?')) {
					isConcat = true;
				}//end if
				else {
					isConcat = false;
				}//end else
			}//end else
		}//end for loop
		
		/**
		 * Evaluate the rest of the operators by popping them off the stack
		 */
		while (!operatorStack.empty()) {
			operatorEvaluator();
		}//end while
		
		return (ArrayList)expressionStack.pop();
	}//end method ConvertToNFA
	
	/**
	 * Checks to see if the input token is an operator
	 * @param ch Character to be tested
	 * @return true if the input character is a * or |
	 */
	private boolean checkForOperator(char ch) {
		return ((ch == '*') || (ch == '|') || (ch == '+') || (ch == '?') || (ch == '$'));
	}//end method checkForOperator
	
	@SuppressWarnings("unused")
	private boolean checkForInputToken(char ch) {
	
		return(!checkForOperator(ch) && !checkForRightParen(ch) && !checkForLeftParen(ch));
		
	}//end method checkForInputToken
	
	/**
	 * Checks to see if the input token is a right parenthesis
	 */
	private boolean checkForRightParen(char ch) {
		return (ch == ')');
	}//end method checkForRightParen
	
	/**
	 * Checks to see if the input token is a left parenthesis
	 */
	private boolean checkForLeftParen(char ch) {
		return (ch == '(');
	}//end method checkForLeftParen
	
	/**
	 * Checks to see if the input token is an input character as
	 * opposed to an operator.  Anything that isn't an operator
	 * will be considered an input character.
	 */
	private boolean isInputToken(char ch) {
		return (!checkForOperator(ch) && !checkForRightParen(ch) && !checkForLeftParen(ch));
	}//end method isInputToken
	
	/**
	 * Checks for operator precedence
	 */
	private int compareOperator(char firstOperator, char secondOperator) {
	
		/** Check for equality first */
		if (firstOperator == secondOperator)
			return 0;
		
		/** Right parenthesis has the highest priority */
		if (firstOperator == ')')
			return 1;
		if (secondOperator == ')')
			return -1;
		
		/** The star operator is after parenthesis */
		if (firstOperator == '*')
			return 1;
		if (secondOperator == '*')
			return -1;
		
		/** Check for question mark */
		if (firstOperator == '?')
			return 1;
		if (secondOperator == '?')
			return -1;
		
		/** Check for the plus operator, represented as '$' */
		if (firstOperator == '$')
			return 1;
		if (secondOperator =='$')
			return -1;
		
		/** If it's not equal and not a star */
		if (firstOperator == '+')
			return 1;
		if (secondOperator == '+')
			return -1;
		
		/** The left parenthesis has the lowest priority */
		if (firstOperator == '|')
			return 1;
		else return -1;
	}//end method compareOperator
	
	/**
	 * Evaluates the operator from the top of the operator stack
	 */
	private void operatorEvaluator () {
		
		/** First pop the operator off the stack */
		Character opChar = (Character)operatorStack.pop();
		
		//System.out.println("Eval " + opChar.toString());
		
		switch (opChar.charValue()) {
			case '*':
				evalStar();
				break;
			case '|':
				evalUnion();
				break;
			case '+':
				evalConcat();
				break;
			case '?':
				evalQmark();
				break;
			case '$':
				evalPlus();
				break;
		}//end switch
	}//end method operatorEvaluator
	
	/**
	 * Evaluate the star operator
	 */
	@SuppressWarnings("unchecked")
	private void evalStar() {

		/** Grab the operands */
		ArrayList theOperand = (ArrayList)expressionStack.pop();
		
		/** Create two additional states */
		State firstState = new State("s" + Integer.toString(nextStateIndex));
		
		/** Increment the state index */
		++nextStateIndex;
		
		State secondState = new State("s" + Integer.toString(nextStateIndex));
		++nextStateIndex;
		
		/** 
		 * Create transitions from firstState to the first state of 
		 * the operand and from firstState to the secondState
		 */
		Transition epsilonTransition1 = new Transition("epsilon");
		epsilonTransition1.stateArray.add(theOperand.get(0));
		epsilonTransition1.stateArray.add(secondState);
		firstState.transitionsArray.add(epsilonTransition1);
		
		/** 
		 * Add transitions from the last element to the operand
		 * and the secondState
		 */
		Transition epsilonTransition2 = new Transition("epsilon");
		epsilonTransition2.stateArray.add(secondState);
		((State)theOperand.get(theOperand.size() - 1)).transitionsArray.add(epsilonTransition2);
		
		/**
		 * Add the epsilon transition between last and first state of the operand
		 */
		Transition epsilonTransition3 = new Transition("epsilon");
		epsilonTransition3.stateArray.add(theOperand.get(0));
		((State)theOperand.get(theOperand.size() - 1)).transitionsArray.add(epsilonTransition3);
		
		/** Generate the new expression */
		ArrayList newExpression = new ArrayList();
		newExpression.add(firstState);
		newExpression.addAll(theOperand);
		newExpression.add(secondState);
		
		/** Push it onto the stack */
		expressionStack.push(newExpression);
	}//end method evalStar
	
	/**
	 * Evaluate the union operator
	 */
	@SuppressWarnings("unchecked")
	private void evalUnion() {
		/** First get the operands */
		ArrayList secondExpression = (ArrayList)expressionStack.pop();
		ArrayList firstExpression = (ArrayList)expressionStack.pop();
		
		/** Create two new states */
		State firstState = new State("s" + Integer.toString(nextStateIndex));
		++nextStateIndex;
		State secondState = new State("s" + Integer.toString(nextStateIndex));
		++nextStateIndex;
		
		/** 
		 * Create the epsilon transitions from the first state to the first state
		 * of the operands
		 */
		Transition epsilonTransition1 = new Transition("epsilon");
		epsilonTransition1.stateArray.add(firstExpression.get(0));
		Transition epsilonTransition2 = new Transition("epsilon");
		epsilonTransition2.stateArray.add(secondExpression.get(0));
		
		/** Add both transitions to the first state */
		firstState.transitionsArray.add(epsilonTransition1);
		firstState.transitionsArray.add(epsilonTransition2);
		
		/** Add transitions from the last state in each operand to the second state */
		Transition epsilonTransition3 = new Transition("epsilon");
		epsilonTransition3.stateArray.add(secondState);
		Transition epsilonTransition4 = new Transition("epsilon");
		epsilonTransition4.stateArray.add(secondState);
		((State)firstExpression.get(firstExpression.size() - 1)).transitionsArray.add(epsilonTransition3);
		((State)secondExpression.get(secondExpression.size() - 1)).transitionsArray.add(epsilonTransition4);
		
		/** Create the expression to push on the stack and push it */
		ArrayList newExpression = new ArrayList();
		newExpression.add(firstState);
		newExpression.addAll(firstExpression);
		newExpression.addAll(secondExpression);
		newExpression.add(secondState);
		expressionStack.push(newExpression);
	}//end method evalUnion
	
	/**
	 * Evalute the concatenation operator to concatenate two elements
	 * from the top of the input stack.
	 */
	@SuppressWarnings("unchecked")
	private void evalConcat() {
		ArrayList secondExpression = (ArrayList)expressionStack.pop();
		ArrayList firstExpression = (ArrayList)expressionStack.pop();
		
		
		/** 
		 * Create epsilon transitions between the last state in the first expression
		 * and the first state in the second expression
		 */
		Transition t = new Transition("epsilon");
		
		t.stateArray.add((State)secondExpression.get(0));
		
		State s = (State)firstExpression.get(firstExpression.size() - 1);
		
		s.transitionsArray.add(t);
				
		/** Construct the expression to put on the stack */
		ArrayList newExpression = new ArrayList();
		newExpression.addAll(firstExpression);
		newExpression.addAll(secondExpression);
		expressionStack.push(newExpression);
		
	}//end method evalConcat
	
	/**
	 * Evaluates the plus operator which is represented by a '$' on the operator stack
	 */
	private void evalPlus() {
		/** Grab the operands */
		ArrayList theOperand = (ArrayList)expressionStack.pop();
		
		/** Create two additional states */
		State firstState = new State("s" + Integer.toString(nextStateIndex));
		
		/** Increment the state index */
		++nextStateIndex;
		
		State secondState = new State("s" + Integer.toString(nextStateIndex));
		++nextStateIndex;
		
		/** 
		 * Create transitions from firstState to the first state of 
		 * the operand and from firstState to the secondState
		 */
		Transition epsilonTransition1 = new Transition("epsilon");
		epsilonTransition1.stateArray.add(theOperand.get(0));
		epsilonTransition1.stateArray.add(secondState);
		firstState.transitionsArray.add(epsilonTransition1);
		
		/** 
		 * Add transitions from the last element to the operand
		 * and the secondState
		 */
//		Transition epsilonTransition2 = new Transition("epsilon");
//		epsilonTransition2.stateArray.add(secondState);
//		((State)theOperand.get(theOperand.size() - 1)).transitionsArray.add(epsilonTransition2);
		
		/**
		 * Add the epsilon transition between last and first state of the operand
		 */
		Transition epsilonTransition3 = new Transition("epsilon");
		epsilonTransition3.stateArray.add(theOperand.get(0));
		((State)theOperand.get(theOperand.size() - 1)).transitionsArray.add(epsilonTransition3);
		
		/** Generate the new expression */
		ArrayList newExpression = new ArrayList();
		newExpression.add(firstState);
		newExpression.addAll(theOperand);
		newExpression.add(secondState);
		
		/** Push it onto the stack */
		expressionStack.push(newExpression);
	}//end method evalPlus
	
	/**
	 * Evaluates the question mark operator
	 */
	@SuppressWarnings("unchecked")
	private void evalQmark() {
		/** Grab the operands */
		ArrayList theOperand = (ArrayList)expressionStack.pop();
		
		/** Create two additional states */
		State firstState = new State("s" + Integer.toString(nextStateIndex));
		
		/** Increment the state index */
		++nextStateIndex;
		
		State secondState = new State("s" + Integer.toString(nextStateIndex));
		++nextStateIndex;
		
		/** 
		 * Create transitions from firstState to the first state of 
		 * the operand and from firstState to the secondState
		 */
		Transition epsilonTransition1 = new Transition("epsilon");
		epsilonTransition1.stateArray.add(theOperand.get(0));
		epsilonTransition1.stateArray.add(secondState);
		firstState.transitionsArray.add(epsilonTransition1);
		
		/** 
		 * Add transitions from the last element to the operand
		 * and the secondState
		 */
		Transition epsilonTransition2 = new Transition("epsilon");
		epsilonTransition2.stateArray.add(secondState);
		((State)theOperand.get(theOperand.size() - 1)).transitionsArray.add(epsilonTransition2);
		
		/** Generate the new expression */
		ArrayList newExpression = new ArrayList();
		newExpression.add(firstState);
		newExpression.addAll(theOperand);
		newExpression.add(secondState);
		
		/** Push it onto the stack */
		expressionStack.push(newExpression);
	}//end method evalQmark
	
	/**
	 * Push 2 states on the stack along with a transition between the two based on
	 * the input character passed in
	 */
	@SuppressWarnings("unchecked")
	private void inputStackPush(String inputChar) {
		ArrayList arrayExpression = new ArrayList();
		
		/** Create state1 */
		String state1Name = "s" + Integer.toString(nextStateIndex);
		State state1 = new State(state1Name);
		++nextStateIndex;
		
		/** Create state2 */
		String state2Name = "s" + Integer.toString(nextStateIndex);
		State state2 = new State(state2Name);
		//++nextStateIndex;
		
		/** Create the transition between the two */
		Transition t = new Transition(inputChar);
		t.stateArray.add(state2);
		state1.transitionsArray.add(t);
		
		/** Add the states to the array */
		arrayExpression.add(state1);
		arrayExpression.add(state2);
		
		/** Push the array object onto the input stack */
		expressionStack.push(arrayExpression);

		/** Increase the state index */
		++nextStateIndex;
		
		/** Add it to the input list */
		treeSetInput.add(inputChar);
	}//end method inputStackPush
}//end class Parser



